/**
  * @file:queue.hpp
  * Implementation of queue
  * Queue is based on a linked list
  */
/**
 *
 * Copyright 2013 MIPT-COMPILER team
 */

#pragma once

#include <cassert>
#include <cstdlib>

/**
 * Class for the queue. Based on creating linked list.
 * Contains pointers to the beginning and the end of the queue.
 * The queue is built for the elements of type T.
 */
template< class T >
class Queue
{
private:
    /** 
      * Structure of one element in the queue.
      * Contains a user-defined type and
      * a pointer to the next element in the queue.
      */
    struct Element
    {
        Element* next;
        T data;
        /** next - pointer to the next element of the queue */
        Element( const T &_data) : next( NULL), data( _data)
        {}
    };
    /** Pointer to the first element of the queue */
    Element* head;
    /** Pointer to the last element of the queue */
    Element* tail;
    /** Count of elements in the queue, = 0 after the constructor */
    size_t qsize;
public:
    Queue();
    Queue( const Queue &q);
    ~Queue();
    /** Add an element to the queue with value = new_elem */
    void push( const T &data);
    /** Extraction of element */
    void pop();
    /** Delete all elements from the queue */
    void clear();
    /** Size of the queue */
    inline size_t size() const;
    /** If the queue is empty return 1 (else 0) */
    inline bool empty() const;
    /** Return first element from the queue. Doesn't remove it */
    inline const T& front() const;
    /** Return last element from the queue. Doesn't remove it */
    inline const T& back() const;
    Queue& operator=( const Queue &q2);    
};

template< class T >
Queue<T>::Queue() : head( NULL), tail( NULL), qsize( 0)
{}

template< class T >
Queue<T>::Queue( const Queue<T> &q) : head( NULL), tail( NULL), qsize( 0)
{
    /* cur_elem - current element to step through the q */
    Element* cur_elem = q.head;
    for ( unsigned int i = 1; i <= q.size(); i++ )
    {
        push( cur_elem->data);
        cur_elem = cur_elem->next;
    }
}

template< class T >
Queue<T>::~Queue()
{
    clear();
}

template< class T >
void Queue<T>::clear()
{
    while ( !empty() )
        pop();
}

/*
 * Add element in the queue.
 * Function takes an element "data" of a user-defined type.
 * Сreates another structure "Element" with "data"
 * And links the queue with the new Element
 */
template< class T >
void Queue<T>::push( const T &data)
{
    Element* new_elem = new Element( data);
    if ( empty() )
    {
        tail = new_elem;
        head = new_elem;
    } else
    {
        tail->next = new_elem;
        tail = new_elem;
    }
    qsize++;
}

/*
 * Remove element from the queue
 */
template< class T >
void Queue<T>::pop()
{
    /* If the queue is empty, the program is terminated */
    assert( !empty());
    Element* cur_elem = head;
    if ( head == tail )
    {
        head = NULL;
        tail = NULL;
    } else
    {
        head = head->next;
    }
    delete cur_elem;
    qsize--;
}

template< class T >
inline size_t Queue<T>::size() const
{
    return (qsize);
}

template< class T >
inline bool Queue<T>::empty() const
{
    return (qsize == 0);
}

/**
 * Return first element from the queue. Doesn't remove it
 */
template< class T >
inline const T& Queue<T>::front() const
{
    assert( !empty());
    return (head->data);
}

/** 
 * Return last element from the queue. Doesn't remove it
 */
template< class T >
inline const T& Queue<T>::back() const
{
    assert( !empty());
    return (tail->data);
}

template< class T >
Queue<T>& Queue<T>::operator=( const Queue<T> &q2)
{
    /* Correct handling of "q = q" */
    if ( this != &q2 )
    {
        clear();
        Element* cur_elem = q2.head;
        while (cur_elem != NULL)
        {
            push( cur_elem->data);
            cur_elem = cur_elem->next;
        }
    }
    return (*this);
}
